//
// Created by Administrator on 2023/11/18.
//
#include "iostream"
#include "cstring"

using namespace std;

const int N = 500, M = 1e4 + 10;

int n, m, k;

struct Edge {
    int from;
    int to;
    int weight;
} edge[M];

int dist[N], backup[N];

void bellman_ford() {
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    //每次循环可以确定一条边
    for (int i = 0; i < k; ++i) {
        //边是随机更新的 每次更新仅仅依赖于上次更新的内容 不受本次更新影响
        memcpy(backup, dist, sizeof dist);

        //遍历边 进行松弛 backup不受影响
        for (int j = 0; j < m; ++j) {
            int from = edge[j].from;
            int to = edge[j].to;
            int w = edge[j].weight;

            //backup 是上次更新的结果 这次根据上次结果进行更新
            dist[to] = min(dist[to], backup[from] + w);
        }
    }
    //a->b 是-2 a不可达为0x3f，但是dist[b]会被更新成 0x3f-2
    if (dist[n] > 0x3f3f3f3f / 2) cout << ("impossible");
    else cout << dist[n];

}


int main() {
    cin >> n >> m >> k;

    for (int i = 0; i < m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        edge[i] = {x, y, z};
    }
    bellman_ford();

}